package com.goldsprite.gdxcore.utils.sorts;

import java.util.*;

public class OptimizedInsertionSort {
    static int comparisons = 0; // 统计比较次数
    static int insertions = 0;  // 统计插入次数

    public static void main(String[] args) {
        ArrayList<Float> sortedList = new ArrayList<>();
		
		long seed = 999; 
        int count = 50, size = 100;
        float[] newValues = RandomFloatArrayGenerator.generateRandomFloatArray(count, -size, size, seed);
		
        for (float value : newValues) {
            insertValue(sortedList, value);
        }
		
		List<Float> originList = new ArrayList<>();
        for (float val : newValues) {
            originList.add(val);
        }
        System.out.println("origin List: " + originList);
		
        System.out.println("Sorted List: " + sortedList);
        System.out.println("Total Comparisons (Estimated): " + comparisons);
        System.out.println("Total Insertions: " + insertions);
    }

    // 插入值到列表中
    public static void insertValue(ArrayList<Float> sortedList, float value) {
        if (sortedList.isEmpty()) {
            sortedList.add(value);
            insertions++;
            return;
        }

        // 使用 Java 提供的二分查找
        int pos = Collections.binarySearch(sortedList, value);
        comparisons += (int) (Math.log(sortedList.size()) / Math.log(2)) + 1; // 二分查找的比较次数大约是 log(n)

        // 如果没有找到，binarySearch 返回 (-插入点 - 1)，需要计算插入位置
        if (pos < 0) {
            pos = -pos - 1;
        }

        sortedList.add(pos, value); // 插入到正确位置
        insertions++;
    }
}

